import queue

def dfs(adj):
    parent = {}

    def visit_rec(u):
        for v in adj[u]:
            if v not in parent:
                parent[v] = u
                visit_rec(v)

    def visit(u):
        stack = [u]
        while stack:
            node = stack[-1]
            cont = False
            for v in adj[node]:
                if v not in parent:
                    parent[v] = node
                    stack.append(v)
                    cont = True
                    break
            if cont:
                continue
            stack.pop()

    for u in adj:
        if u not in parent:
            parent[u] = None
            visit(u)

    return parent

if __name__ == '__main__':
    adj = \
    {
        'a': ['b', 'd'],
        'b': ['a', 'd', 'f'],
        'c': ['e'],
        'd': ['a', 'b'],
        'e': ['c'],
        'f': ['b', 'g'],
        'g': ['f']
    }

    print (dfs(adj))